﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdbool.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>

//A65
//a=97,z=122
//给定两个由小写字母组成的字符串 s1 和 s2，
//请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
//bool CheckPermutation(char* s1, char* s2)
//{
//	int Len1 = strlen(s1);
//	int Len2 = strlen(s2);
//	if (Len1 != Len2)
//		return false;
//	int arr1[26] = { 0 };
//	int arr2[26] = { 0 };
//	while (*s1)
//	{
//		arr1[*s1 - 97]++;
//		arr2[*s2 - 97]++;
//		s1++;
//		s2++;
//	}
//	for (int i = 0; i < 26; i++)
//	{
//		if (arr1[i] != arr2[i])
//			return false;
//	}
//	return true;
//}

//int hammingWeight(uint32_t n) {
//	int i = 0;
//	int flag = 0;
//	for (i = 0; i < 32; i++)
//	{
//		if ((n >> i) % 2)
//		{
//			flag++;
//		}
//	}
//	return flag;
//}

//在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
//char firstUniqChar(char* s) {
//    int i, hash[26] = { 0 };
//    for (i = 0; i < strlen(s); i++) {
//        hash[s[i] - 'a']++;
//    }
//    for (i = 0; i < strlen(s); i++) {
//        if (hash[s[i] - 'a'] == 1)//判断是否是第一个只出现一次的字符。
//            return s[i];
//    }
//    return ' ';
//}

//给定一个字符串 s ，验证 s 是否是 回文串 ，
//只考虑字母和数字字符，可以忽略字母的大小写。
//bool isPalindrome(char* s)
//{
//	int len = strlen(s);
//	char* p1 = (char*)malloc(len + 1);
//	int i = 0;
//	int arr[128] = { 0 };
//	while (*s)
//	{
//		if ((*s >= 'a' && *s <= 'z') || (*s >= 'A' && *s <= 'Z')||(*s>='0'&&*s<='9'))
//		{
//			if (*s >= 'A' && *s <= 'Z')
//				*s = *s + 'a' - 'A';
//			p1[i] = *s;
//			i++;
//		}
//		s++;
//	}
//	p1[i] = '\0';
//	int left = 0;
//	int right = strlen(p1)-1;
//	while (left <= right)
//	{
//		if (p1[right] == p1[left])
//		{
//			left++;
//			right--;
//		}
//		else
//			return false;
//	}
//	return true;
//}
//int main()
//{
//	char s[] = "A man, a plan, a canal: Panama";
//	int ret=isPalindrome(s);
//	printf("%d", ret);
//	return 0;
//}

//char* largestGoodInteger(char* num)
//{
//    char temp[10][4] = { "999", "888", "777", "666", "555", "444", "333", "222", "111", "000" };
//    for (int i = 0; i < 10; i++) {
//        if (strstr(num, temp[i]) != NULL) {
//            return temp[i];
//        }
//    }
//    return "";
//}

//检查句子中的数字是否是递增的/
//完成
//int is_dizheng(int* arr, int num)
//{
//	for (int i = 0; i < num-1; i++)
//	{
//		if (arr[i] < arr[i + 1])
//			continue;
//		else
//			return 0;
//	}
//	return true;
//}
//
//bool areNumbersAscending(char* s) 
//{
//	int arr[300] = { 0 };
//	int flag = 0;
//	while (*s)
//	{
//		int i = 0;
//		int sum = 0;
//		int flag1 = 0;
//		if (*s <= '9' && *s >= '0')
//		{
//			char* s1 = s;
//			while (*s1 <= '9' && *s1 >= '0'&&*s)
//			{
//				i++;
//				s1++;
//			}
//			while (*s <= '9' && *s >= '0'&&*s)
//			{
//				sum += (*s - '0') * (pow(10, i - 1));
//				i--;
//				s++;
//				flag1++;
//			}
//			arr[flag] = sum;
//			flag++;
//		}
//		if (flag1 == 0)
//		{
//			s++;
//		}
//		num++;
//	}
//	int ret=is_dizheng(arr, flag);
//	if (ret == 1)
//	{
//		return true;
//	}
//	else
//	{
//		return false;
//	}
//}
//int main()
//{
//	char s[] = "hello world 5 x 5";
//	int sz = sizeof(s) / sizeof(*s);
//	int ret = areNumbersAscending(s);
//	return 0;
//}

//判断出现的数字是否是递增
//int CheckAndGetNum(char* str) {
//    // 是数字
//    if (str[0] >= '0' && str[0] <= '9') {
//        return atoi(str);
//    }
//    return -1;
//}
//
//bool areNumbersAscending(char* s) {
//    char split[2] = " ";
//    char* token = strtok(s, split);
//    int ans = -1;
//    while (token != NULL) {
//        int res = CheckAndGetNum(token);
//        if (res != -1) {
//            if (ans >= res) {
//                return false;
//            }
//            ans = res;
//        }
//        token = strtok(NULL, split);
//    }
//    return true;
//}
//int main()
//{
//	char s[] = "hello world 5 x 5";
//	int sz = sizeof(s) / sizeof(*s);
//	int ret = areNumbersAscending(s);
//    printf("%d", ret);
//	return 0;
//}

//给你一个字符串数组 words ，找出并返回数组中的 第一个回文字符串 。如果不存在满足要求的字符串，返回一个 空字符串 "" 。
//回文字符串 的定义为：如果一个字符串正着读和反着读一样，那么该字符串就是一个 回文字符串 。
//int test(char* str)
//{
//	int len = strlen(str);
//	int right = len - 1;
//	int left = 0;
//	while (right >= left)
//	{
//		if (str[right] == str[left])
//		{
//			right--;
//			left++;
//		}
//		else
//			return 0;
//	}
//	return 1;
//}
//
//char* firstPalindrome(char** words, int wordsSize) {
//	int i = 0;
//	for (i = 0; i < wordsSize; i++)
//	{
//		int ret = test(words[i]);
//		if (ret == 1)
//		{
//			return words[i];
//		}
//	}
//	return "";
//}

//给你一个字符串 s ，如果 s 是一个 好 字符串，请你返回 true ，否则请返回 false 。
//如果 s 中出现过的 所有 字符的出现次数 相同 ，那么我们称字符串 s 是 好 字符串。
//输入：s = "abacbc"
//输出：true
//解释：s 中出现过的字符为 'a'，'b' 和 'c' 。s 中所有字符均出现 2 次。
//bool areOccurrencesEqual(char* s) {
//	int arr[26] = { 0 };
//	int len = strlen(s);
//	int flag = 0;
//	while (*s)
//	{
//		arr[*s - 'a']++;
//		s++;
//	}
//	for (int i = 0; i < 26; i++)
//	{
//		if (arr[i] != 0)
//		{
//			if (flag == 0)
//			{
//				flag = arr[i];
//			}
//			else
//			{
//				if (arr[i] != flag)
//				{
//					return false;
//				}
//			}
//		}
//	}
//	return true;
//}
//int main()
//{
//	char p1[] = "wzkpzzwzpzkwkpkppzkppkpkwwkzzzwwpwwk";
//	int ret = areOccurrencesEqual(p1);
//	printf("%d", ret);
//	return 0;
//}

//给你一个二进制字符串 s ，该字符串 不含前导零 。
//如果 s 包含 零个或一个由连续的 '1' 组成的字段 ，返回 true​​​ 。否则，返回 false 。
//bool checkOnesSegment(char* s) {
//	int len = strlen(s);
//	int* arr = (int*)malloc(sizeof(int) * len);
//	int i = 0;
//	int flag = 0;
//	for (i = 0; i < len; i++)
//	{
//		arr[i] = s[i] - '0';
//	}
//	if (*s != 0)
//	{
//		flag++;
//	}
//	for (i = 1; i < len; i++)
//	{
//		if (arr[i] != 0 && arr[i - 1] == 0)
//		{
//			flag++;
//		}
//	}
//	if (flag > 1)
//		return false;
//	return true;
//}
//int main()
//{
//	char p[] = "1101";
//	int ret = checkOnesSegment(p);
//	printf("%d", ret);
//	return 0;
//}

//给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。
//注意：你 不能 修改非 '?' 字符。
//题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。
//在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。
// 可以证明，在给定的约束条件下，答案总是存在的。
// 还差一个要求
//void test(int* arr, int num)
//{
//	for (int i = 0; i < num; i++)
//	{
//		arr[i] = 0;
//	}
//}
//char* modifyString(char* s) {
//	int arr[26] = { 0 };
//	int i = 0;
//	int len = strlen(s);
//	for (i = 0; i < len; i++)
//	{
//		if (s[i] >= 'a' && s[i] <= 'z')
//			arr[s[i] - 'a']++;
//	}
//	int j = 0;
//	for (i = 0; i < len; i++)
//	{
//		if (s[i] == '?')
//		{
//			for (j ; j < 26; j++)
//			{
//				if (arr[j] == 0)
//				{
//					s[i] = j + 'a';
//					arr[j]++;
//					break;
//				}
//			}
//			if (j == 26 && i < len)
//			{
//				s[i] = 'a';
//				j = 0;
//				test(arr, 26);
//				arr[j]++;
//			}
//		}
//	}
//	return s;
//}
//int main()
//{
//	char p[] = "????????????????????????????????????????????????????????????????????????????????????????????????????";
//	modifyString(p);
//	printf("%s", p);
//	return 0;
//}

//char* modifyString(char* s) 
//{
//    for (int i = 0; s[i] != '\0'; ++i) 
//    {
//        if (s[i] == '?') 
//        {
//            char ch = 'a';
//            while ((i > 0 && ch == s[i - 1]) || (s[i + 1] != '\0' && ch == s[i + 1])) 
//            {
//                //ch++操作开销比 ++ch 大，因此这里用 ++ch 优化
//                //ch++;
//                ++ch;
//            }
//            s[i] = ch;
//        }
//    }
//    return s;
//}
//int main()
//{
//	char p[] = "????????????????????????????????????????????????????????????????????????????????????????????????????";
//	modifyString(p);
//	printf("%s", p);
//	return 0;
//}

//void test(int num, int* returnSize)
//{
//	int i = 0;
//	while (num)
//	{
//		num /= 10;
//		i++;
//	}
//	if (i % 2 == 0)
//		(*returnSize)++;
//}
//int findNumbers(int* nums, int numsSize) 
//{
//	int i = 0;
//	int flag = 0;
//	for (i = 0; i < numsSize; i++)
//	{
//		test(nums[i], &flag);
//	}
//	return flag;
//}
//int main()
//{
//	int arr[] = { 123,12,24,12345 };
//	int ret = findNumbers(arr, 4);
//	printf("%d", ret);
//	return 0;
//}

//给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。
//请你返回 nums 中唯一元素的 和 。
//int sumOfUnique(int* nums, int numsSize) {
//	int arr[101] = { 0 };
//	int i = 0;
//	int sum = 0;
//	for (i = 0; i < numsSize; i++)
//	{
//		arr[nums[i]]++;
//	}
//	for (i = 0; i < 101; i++)
//	{
//		if (arr[i]==1)
//		{
//			sum += i;
//		}
//	}
//	return sum;
//}


//力扣跑不动，Vs跑的动。

//int test(int num)
//{
//	int i = 0;
//	int sum = 0;
//	while (num)
//	{
//		sum += pow((num % 10), 2);
//		num /= 10;
//	}
//	if (sum < 10)
//	{
//		return sum;
//	}
//	else
//	{
//		test(sum);
//	}
//}
//
//bool isHappy(int n) 
//{
//	int ret = test(n);
//	if (ret==1)
//		return true;
//	return false;
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int ret = isHappy(n);
//	printf("%d", ret);
//	return 0;
//}

//字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
//（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
//bool isSubsequence(char* s, char* t)
//{
//	int sLen = strlen(s);
//	int tLen = strlen(t);
//	if (sLen == tLen && sLen == 0)
//		return true;
//	if (sLen > tLen)
//		return false;
//	else
//	{
//		while (*t)
//		{
//			if (*s == *t)
//			{
//				s++;
//			}
//			if (*s == 0)
//				return true;
//			t++;
//		}
//	}
//	return false;
//}
//int main()
//{
//	char s[] = "abc";
//	char t[] = "adebdeaxc";
//	int ret = isSubsequence(s, t);
//	printf("%d", ret);
//	return 0;
//}

//给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
//请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。
//如果是，则返回 最大元素的下标 ，否则返回 - 1 。
//
//void test(int* arr, int* nums, int numsSize)
//{
//	int i = 0;
//	for (i = 0; i < numsSize; i++)
//	{
//		arr[i] = nums[i];
//	}
//}
//
//void yuanshen(int* arr, int numsSize)
//{
//	int i = 0;
//	int j = 0;
//	for (i = 0; i < numsSize-1; i++)
//	{
//		for (j = i + 1; j < numsSize; j++)
//		{
//			if (arr[i] > arr[j])
//			{
//				int tmp = arr[i];
//				arr[i] = arr[j];
//				arr[j] = tmp;
//			}
//		}
//	}
//}
//
//int dominantIndex(int* nums, int numsSize) {
//	int* arr = (int*)malloc(sizeof(int) * numsSize);
//	test(arr, nums, numsSize);
//	yuanshen(arr, numsSize);
//	int i = 0;
//	int ret = arr[numsSize - 1] - 2 * arr[numsSize - 2];
//	if (ret >= 0)
//	{
//		for (i = 0; i < numsSize; i++)
//		{
//			if (nums[i] == arr[numsSize - 1])
//				return i;
//		}
//	}
//	return -1;
//}
//int main()
//{
//	int arr[] = { 1,3,6,0 };
//	int ret = dominantIndex(arr, 4);
//	return 0;
//}

//给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
//请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
//任何误差小于 10 - 5 的答案都将被视为正确答案。

//超出时间限制
//double test(int* arr, int x, int y)
//{
//	int i = 0;
//	double sum = 0;
//	for (i = x; i < x+y; i++)
//	{
//		sum += arr[i];
//	}
//	return sum;
//}
//
//double findMaxAverage(int* nums, int numsSize, int k) {
//	double sum = 0;
//	double max = 0;
//	int i = 0;
//	for (i = 0; i <= numsSize - k; i++)
//	{
//		sum = 0;
//		sum += test(nums, i, k);
//		if (max == 0)
//			max = sum;
//		else
//		{
//			if (max < sum)
//				max = sum;
//		}
//	}
//	return max / k;
//}
//int main()
//{
//	int arr[] = { 1, 12, -5, -6, 50, 3 };
//	double ret = findMaxAverage(arr, 6, 4);
//	printf("%lf", ret);
//	return 0;
//}

//double findMaxAverage(int* nums, int numsSize, int k) {
//    int i, j;
//    double max = 0, sum;
//    for (i = 0; i < k; i++)
//        max += nums[i];
//    sum = max;
//    if (k != numsSize) 
//    {
//        for (i = 1; i <= numsSize - k; i++) 
//        {
//            sum = sum - nums[i - 1] + nums[i + k - 1];
//            max = max > sum ? max : sum;
//        }
//    }
//    return max / k;
//}

//输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
//int* reversePrint(struct ListNode* head, int* returnSize) {
//	int flag = 0;
//	struct ListNode* p1 = head;
//	while (p1->next)
//	{
//		flag++;
//		p1 = p1->next;
//	}
//	flag++;
//	int* arr = (int*)malloc(sizeof(int) * flag);
//	while (head)
//	{
//		arr[falg - 1] = head->val;
//		flag--;
//		head = head->next;
//	}
//	return arr;
//}

//bool checkIfPangram(char* sentence) {
//	int len = strlen(sentence);
//	if (s < 26)
//		return false;
//	int arr[26] = { 0 };
//	int flag = 0;
//	while (*sentence)
//	{
//		if (arr[*sentence - 'a']==0)
//		{
//			flag++;
//		}
//		if (flag == 26)
//		{
//			return true;
//		}
//		arr[*sentence - 'a']++;
//		sentence++;
//	}
//	return false;
//}

//给你一个表示某个正整数的字符串 number 和一个字符 digit 。
//从 number 中 恰好 移除 一个 等于 digit 的字符后，找出并返回按 十进制 表示 最大 的结果字符串。
//生成的测试用例满足 digit 在 number 中出现至少一次。
char* removeDigit(char* number, char digit) {
    int n = 0;
    int len = strlen(number);
    char* sum = (char*)malloc(sizeof(char) * len);
    char* max = (char*)malloc(sizeof(char) * len);
    sum[len - 1] = '\0';
    max[len - 1] = '\0';
    max[0] = 0;//这里去掉就不行了
    for (int i = 0; i < len; i++) 
    {
        if (number[i] == digit) 
        {
            if (i == 0) 
            {
                memcpy(sum, &number[1],(len - 1) * sizeof(char));
            }
            else 
            { 
                memcpy(sum, &number[0], (i) * sizeof(char)); 
                memcpy(&sum[i], &number[i + 1], (len - i) * sizeof(char)); 
            }

            int ss = strcmp(sum, max);
            if (ss > 0)
                memcpy(max, sum, (len - 1) * sizeof(char));
        }
    }
    return max;
}